{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 什么是栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "栈(有时称为“后进先出栈”)是一个项的有序集合,其中添加移除新项总发生在同一端。这一端通常称为“顶部”。与顶部对应的端称为“底部”。\n",
    "\n",
    "<img src=\"image/chapter01/Screenshot from 2018-03-29 20-35-51.png\" width=400>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "本着后进先出(LIFO)的原则，那么它应该是 \n",
    "\n",
    "<img src=\"image/chapter01/Screenshot from 2018-03-29 20-38-11.png\" width=500>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "    \n",
    "    def push(self,item):\n",
    "        self.items.append(item)\n",
    "        \n",
    "    def pop(self):\n",
    "        return self.items.pop()\n",
    "    \n",
    "    # 访问栈顶部项\n",
    "    def top(self):\n",
    "        return self.items[-1]\n",
    "    \n",
    "    def size(self):\n",
    "        return len(self.items)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 括号匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 简单匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "括号必须以匹配的方式出现。括号匹配意味着每个开始符号具有相应的结束符号,并且括号能被正确嵌套。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\bullet$ 可匹配：\n",
    "<img src = \"image/chapter02/Screenshot from 2018-03-29 22-01-23.png\" width=400>\n",
    "\n",
    "$\\bullet$ 不可匹配：\n",
    "<img src = \"image/chapter02/Screenshot from 2018-03-29 22-01-58.png\" width=400>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parChecker(symbolString):\n",
    "    \n",
    "    # 创建一个栈\n",
    "    s = Stack()\n",
    "    # 从左到右遍历符号\n",
    "    for symbol in symbolString:\n",
    "        \n",
    "        #如果是左括号，就入栈\n",
    "        if symbol == '(':\n",
    "            s.push(symbol)\n",
    "        \n",
    "        #如果是右括号，就拿出一个与之匹配\n",
    "        if symbol == ')':\n",
    "            try:\n",
    "                #匹配成功，那么继续\n",
    "                s.pop() == '('\n",
    "            \n",
    "            except:\n",
    "                #匹配失败，那么返回False\n",
    "                return False\n",
    "    \n",
    "    # 都匹配完了后发现还残留左括号，那么返回False\n",
    "    return True if s.isEmpty() else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((1+2)*3+1)/2 True\n",
      "(10+2)==12 True\n",
      "((3-1)*2)-2) False\n"
     ]
    }
   ],
   "source": [
    "symbolStrings = [\"((1+2)*3+1)/2\",\"(10+2)==12\",\"((3-1)*2)-2)\"]\n",
    "\n",
    "for symbolString in symbolStrings:\n",
    "    print(symbolString,parChecker(symbolString))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 复杂匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面显示的匹配括号问题是许多编程语言都会出现的一般情况的特定情况。匹配和嵌套不同种类的开始和结束符号的情况经常发生，例如\n",
    "\n",
    "<img src = \"image/chapter02/Screenshot from 2018-03-29 22-05-01.png\" width=400>\n",
    "\n",
    "回想一下,其实是这样的：每个开始符号被简单的压入栈中,等待匹配的结束符号出现，当出现结束符号时,唯一的区别是我们必须检查确保它正确匹配栈顶部开始符号的类型；如果两个符号不匹配,则字符串不匹配；如果整个字符串都被处理完并且没有什么留在栈中,则字符串匹配。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parChecker_all(symbolString):\n",
    "    \n",
    "    pattern = [['(',')'],['[',']'],['{','}']] # 匹配的模式\n",
    "    s = Stack()\n",
    "    for symbol in symbolString:\n",
    "        \n",
    "        if symbol in \"([{\": # 如果是开括号，入栈\n",
    "            s.push(symbol)\n",
    "            \n",
    "        if symbol in \")]}\": # 如果是闭括号\n",
    "            try:\n",
    "                ans = [s.pop(),symbol] # 出栈的符号与闭括号匹配\n",
    "                assert ans in pattern #  是否匹配，若匹配则继续\n",
    "            \n",
    "            except:\n",
    "                return False # 不匹配，返回 False\n",
    "    \n",
    "    return True if s.isEmpty() else False\n",
    "\n",
    "#------------------------------- The simplest code ----------------#\n",
    "\n",
    "def ans(S):\n",
    "    L = ['[',\"{\",\"(\"]\n",
    "    Q = {']':'[','}':\"{\",\")\":\"(\"}\n",
    "    R = list(Q.keys())\n",
    "    V = []\n",
    "    for s in S:\n",
    "        if s in L: V.append(s)\n",
    "        if s in R:\n",
    "            if V and V.pop() == Q[s]:continue\n",
    "            return False\n",
    "    return len(V) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[((1+2)*3+1)/2  False\n",
      "{[(10+2)==12,[2,-1],2]} True\n",
      "{'hello':'world',[1,2,(1,(-1,2)]} False\n",
      "=========================================\n",
      "False True False "
     ]
    }
   ],
   "source": [
    "symbolStrings = [\"[((1+2)*3+1)/2 \",\"{[(10+2)==12,[2,-1],2]}\",\n",
    "                 \"{'hello':'world',[1,2,(1,(-1,2)]}\"]\n",
    "\n",
    "for symbolString in symbolStrings:\n",
    "    print(symbolString,parChecker_all(symbolString))\n",
    "\n",
    "print(\"=========================================\")\n",
    "for symbolString in symbolStrings:\n",
    "    print(ans(symbolString), end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 进制转换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【1】 二进制转换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "二进制在计算机科学中是很重要的,   因为存储在计算机内的所有值都是以\t0\t和\t1\t存储的。十进制\t233 对应的二进制为\n",
    "\n",
    "$$233 = 1×2^7+1×2^6+1×2^5+0×2^4+1×2^3+0×2^2+0×2^1+1×2^0$$\n",
    "\n",
    "但是我们如何能够容易地将整数值转换为二进制呢?答案是\t“除\t2”算法,它用栈来跟踪二进制结果的数字。“除\t2”\t算法假定我们从大于\t0\t的整数开始。不断迭代的将十进制除以\t2,并跟踪余数。第一个\n",
    "除以\t2\t的余数说明了这个值是偶数还是奇数。偶数有\t0\t的余数,记为\t0。奇数有余数\t1,记为\n",
    "1.我们将得到的二进制构建为数字序列,第一个余数实际上是序列中的最后一个数字。见\n",
    "下图,\t我们再次看到了反转的属性,表示栈可能是解决这个问题的数据结构。\n",
    "\n",
    "<img src=\"image/chapter02/Screenshot from 2018-03-29 22-14-01.png\" width=650>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "十进制： 233\n",
      "二进制： 11101001\n"
     ]
    }
   ],
   "source": [
    "def divideBy2(decNumber):\n",
    "    \n",
    "    print(\"十进制： {}\".format(decNumber))\n",
    "    s = Stack()\n",
    "    \n",
    "    while decNumber!=0:\n",
    "        s.push(decNumber%2) # 余数入栈\n",
    "        decNumber = decNumber//2  # 跟踪除数\n",
    "    \n",
    "    ans = ''\n",
    "    while not s.isEmpty():\n",
    "        ans = ans + str(s.pop()) # 一个个出栈\n",
    "    \n",
    "    print(\"二进制： {}\".format(ans))\n",
    "    return ans\n",
    "\n",
    "ans = divideBy2(233)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【2】 2~16进制转换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def divideByN(decNumber,N):\n",
    "    \n",
    "    #print(\"十进制： {}\".format(decNumber))\n",
    "    digits = '0123456789ABCDEF'\n",
    "    s = Stack()\n",
    "    \n",
    "    while decNumber!=0:\n",
    "        s.push(decNumber%N) \n",
    "        decNumber = decNumber//N\n",
    "    \n",
    "    ans = ''\n",
    "    while not s.isEmpty():\n",
    "        ans = ans + digits[s.pop()]\n",
    "        \n",
    "    return ans\n",
    "\n",
    "#------------------------------- The simplest code ----------------#\n",
    "\n",
    "def ans(a,n=2):\n",
    "    d = '0123456789ABCDEF'\n",
    "    V = []\n",
    "    while a:\n",
    "        V.append(d[a%n])\n",
    "        a = a//n\n",
    "    return \"\".join(list(reversed(V)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2进制: 11011111, 11011111\n",
      "3进制:    22021,    22021\n",
      "4进制:     3133,     3133\n",
      "5进制:     1343,     1343\n",
      "6进制:     1011,     1011\n",
      "7进制:      436,      436\n",
      "8进制:      337,      337\n",
      "9进制:      267,      267\n",
      "10进制:      223,      223\n",
      "11进制:      193,      193\n",
      "12进制:      167,      167\n",
      "13进制:      142,      142\n",
      "14进制:      11D,      11D\n",
      "15进制:       ED,       ED\n",
      "16进制:       DF,       DF\n"
     ]
    }
   ],
   "source": [
    "# 来看看 233 从 2 到 16 进制的值\n",
    "for N in range(2,17):\n",
    "    print(\"%d进制: %8s, %8s\" %(N, divideByN(223,N), ans(223,N)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 什么是队列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "队列是项的有序结合,其中添加新项的一端称为队尾,移除项的一端称为队首。当一个元素从队尾进入队列时,一直向队首移动,直到它成为下一个需要移除的元素为止。最近添加的元素必须在队尾等待,而集合中存活时间最长的元素在队首,这种排序称为FIFO,先进先出,也被成为先到先得。\n",
    "\n",
    "<img src=\"image/chapter02/Screenshot from 2018-03-30 10-22-21.png\" width=500>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python实现队列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Put into queue:\n",
      "0 <-- 1 <-- 2 <-- 3 <-- 4\n",
      "size = 5\n",
      "Out of queue:\n",
      "0 <-- 1 <-- 2 <-- 3 <-- 4\n"
     ]
    }
   ],
   "source": [
    "from queue import Queue\n",
    "\n",
    "# 创建队列\n",
    "q = Queue()\n",
    "\n",
    "# 进队列\n",
    "print(\"Put into queue:\")\n",
    "for i in range(5):\n",
    "    print(format(i),end=' <-- ' if i != 4 else '\\n')\n",
    "    q.put(i)\n",
    "\n",
    "# 队列元素计数\n",
    "print(\"size = {}\".format(q.qsize()))\n",
    "\n",
    "# 出队列\n",
    "print(\"Out of queue:\")\n",
    "for i in range(5):\n",
    "    print(format(q.get()),end=' <-- ' if i != 4 else '\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 约瑟夫问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一个一世纪著名历史学家弗拉维奥·约瑟夫斯的传奇故事。故事讲的是,他和他的39个战友被罗马军队包围在洞中。他们决定宁愿死,也不成为罗马人的奴隶。他们围成一个圈,其中一人被指定为第一个人,顺时针报数到第七人,就将他杀死。约瑟夫斯是一个成功的数学家,他立即想出了应该坐到哪才能成为最后一人。最后,他加入了罗马的一方,而不是杀了自己。\n",
    "\n",
    "现在，不妨将问题简化下：6个孩子们围成一个圈,并尽可能快的将一个烫手的山芋递给旁边的孩子并报数。在报到N后,动作结束,有山芋的孩子从圈中移除。游戏继续开始直到剩下最后一个孩子。\n",
    "\n",
    "\n",
    "<img src=\"image/chapter02/Screenshot from 2018-03-30 10-36-33.png\" width=500>\n",
    "\n",
    "为了模拟这个圈,我们使用队列假设拿着山芋的孩子在队列的前面。当拿到山芋的时候,这个孩子将先出列再入队列,把他放在队列的最后。经过N次的出队入队后,前面的孩子将被永久移除队列。并且另一个周期开始,继续此过程,直到只剩下一个名字(队列的大小为1)\n",
    "\n",
    "<img src=\"image/chapter02/Screenshot from 2018-03-30 10-45-47.png\" width=500>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 算法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bill 1--> David 2--> Susan 3--> Jane 4--> Kent 5--> Brad 6--> Bill 7\n",
      "OUT:Bill\n",
      "David 1--> Susan 2--> Jane 3--> Kent 4--> Brad 5--> David 6--> Susan 7\n",
      "OUT:Susan\n",
      "Jane 1--> Kent 2--> Brad 3--> David 4--> Jane 5--> Kent 6--> Brad 7\n",
      "OUT:Brad\n",
      "David 1--> Jane 2--> Kent 3--> David 4--> Jane 5--> Kent 6--> David 7\n",
      "OUT:David\n",
      "Jane 1--> Kent 2--> Jane 3--> Kent 4--> Jane 5--> Kent 6--> Jane 7\n",
      "OUT:Jane\n",
      "Survived person = Kent\n"
     ]
    }
   ],
   "source": [
    "from queue import Queue\n",
    "\n",
    "def Josephus(namelist,N):\n",
    "    \n",
    "    q,count = Queue(), 0\n",
    "    # 刚开始的时候，每个人依次入队列\n",
    "    for name in namelist:\n",
    "        q.put(name)\n",
    "        \n",
    "    while q.qsize() > 1:\n",
    "        person = q.get() # 队首的人出队\n",
    "        # print(person)\n",
    "        count += 1 # 报数\n",
    "        print(person,count,end='--> ' if count<N else '\\n')\n",
    "        if count == N: # 如果计数值为N\n",
    "            print(\"OUT:{}\".format(person))\n",
    "            count = 0  # 那么他不能再入队，相当于被踢出游戏了， 此时计数重新开始\n",
    "            continue\n",
    "        \n",
    "        q.put(person) # 如果计数小于N，那么他可以在入队\n",
    "    \n",
    "    return q.get() # 返回队列里的最后一人， 他为存活者！\n",
    "\n",
    "namelist = [\"Bill\",\"David\",\"Susan\",\"Jane\",\"Kent\",\"Brad\"]\n",
    "print(\"Survived person = {}\".format(Josephus(namelist,7)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 什么是 Deque"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "deque(也称为双端队列)是与队列类似的项的有序集合。它有两个端部,首部和尾部,并且项在集合中保持不变。deque\t不同的地方是添加和删除项是非限制性的。可以在前面或后面添加新项。同样,可以从任一端移除现有项。在某种意义上,这种混合线性结构提供了单个数据结构中的栈和队列的所有能力。\n",
    "\n",
    "<img src=\"image/chapter02/Screenshot from 2018-03-30 12-56-46.png\" width=500>\n",
    "\n",
    "\n",
    "deque模块是python标准库collections中的一项，它提供了两端都可以操作的序列，这意味着，在序列的前后你都可以执行添加或删除操作。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([0, 1, 2])\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "iteration = range(3) \n",
    "d = deque(iteration) # 参数为一个迭代器\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【1】 从右边添加一个元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([0, 1, 2, 3])\n"
     ]
    }
   ],
   "source": [
    "d.append(3)\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【2】 从左边添加一个元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([-1, 0, 1, 2, 3])\n"
     ]
    }
   ],
   "source": [
    "d.appendleft(-1)\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【3】 从右边删除一个元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([-1, 0, 1, 2])\n"
     ]
    }
   ],
   "source": [
    "d.pop()\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【4】 从左边删除一个元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([0, 1, 2])\n"
     ]
    }
   ],
   "source": [
    "d.popleft()\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【5】 从右边拼接元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([0, 1, 2, 3, 4])\n"
     ]
    }
   ],
   "source": [
    "d.extend([3,4])\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【6】从左边拼接元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([-1, -2, 0, 1, 2, 3, 4])\n"
     ]
    }
   ],
   "source": [
    "d.extendleft([-2,-1])\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【7】删除指定元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([-1, -2, 1, 2, 3, 4])\n"
     ]
    }
   ],
   "source": [
    "d.remove(0) # 删除 0 \n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【8】复制队列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([-1, -2, 1, 2, 3, 4]) deque([-1, 2, 1, 2, 3, 4])\n"
     ]
    }
   ],
   "source": [
    "d_copy = d.copy()\n",
    "d_copy[1] = 2\n",
    "print(d,d_copy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【9】 队列顺序反转"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([4, 3, 2, 1, -2, -1])\n"
     ]
    }
   ],
   "source": [
    "d.reverse()\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 【10】 队列旋转"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([4, 3, 2, 1, -2, -1])\n",
      "deque([-1, 4, 3, 2, 1, -2])\n",
      "deque([1, -2, -1, 4, 3, 2])\n"
     ]
    }
   ],
   "source": [
    "print(d) # [4, 3, 2, 1, -2, -1]\n",
    "d.rotate(1) # -1 出队，然后跑到队尾\n",
    "print(d) # [-1, 4, 3, 2, 1, -2]\n",
    "d.rotate(2) # -2 出队，跑到队尾，然后 1 出队，又跑到队尾\n",
    "print(d) # [1, -2, -1, 4, 3, 2]"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
